/**
 *	2.质数不能被除了它自己和1的其他任何值整除，写一个程序打印出1-100内所有的质数
**/

#include <stdio.h>
#include <stdlib.h>

/**
 *	 改进点：如果存在数字1能被数字2整除，那么一定存在这样一个小于等于数字1算术平方根的数字2（数学定理），
 *       所以一个数字在2~本身算术平方根这个数字区间内没有遇到能够被整除的数字，那么这个数就不是质数
 *       简单解释一下：因数都是成对出现的。比如，100的因数有：1和100，2和50，4和25，5和20，10和10。
 *       看出来没有？成对的因数，其中一个必然小于等于100的开平方，另一个大于等于100的开平方。
**/
char is_print(char num);

/**
 *	先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。
 * 	第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。
 *	2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。
 *	3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。
 *	这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。
 *	因为希腊人是把数写在涂腊的板上，每要划去一个数，就在上面记以小点，
 *	寻求质数的工作完毕后，这许多小点就像一个筛子，
 *	所以就形象地把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛”，简称“筛法”。
**/
char printPrimeNum(char num);

int main(void)
{
	int i;

	for(i = 1; i < 101; i++)
		if(is_print(i))
			printf("%d ", i);
	printf("\n");

	printPrimeNum(100);
	printf("\n");

	return 0;
}

char is_print(char num)
{
	int i;

	if(num == 1)
		return 0;

	// 改进点：如果存在数字1能被数字2整除，那么一定存在这样一个小于等于数字1算术平方根的数字2（数学定理），
	// 所以一个数字在2~本身算术平方根这个数字区间内没有遇到能够被整除的数字，那么这个数就不是质数
	// 简单解释一下：因数都是成对出现的。比如，100的因数有：1和100，2和50，4和25，5和20，10和10。
	// 看出来没有？成对的因数，其中一个必然小于等于100的开平方，另一个大于等于100的开平方。
	for(i = 2; i * i <= num; i++)
	{
		if(num % i == 0)
			return 0;
	}
	return 1;
}

// 1 - num
char printPrimeNum(char num)
{
	int i, j;
	char *prime;
 
	prime = (char *)malloc(sizeof(char) * (num + 1));
	prime[1] = 0;
	for(i = 2; i <= num; i++)
		prime[i] = 1;

	for(i = 2; i <= num; i++)
	{
		if(prime[i])
		{
			for(j = i + i; j <= num; j += i)
				prime[j] = 0;	
		}
	}

	for(i = 0; i <= num; i++)
		if(prime[i])
			printf("%d ", i);
}
